home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / FATMAP.ZIP / FATMAP.TXT
Encoding:
Text File  |  1997-01-09  |  69.3 KB  |  1,825 lines

  1.  
  2.  
  3.  
  4.             Fast affine texture mapping (fatmap.txt)
  5.             ----------------------------------------
  6.  
  7.                               by
  8.  
  9.                         Mats Byggmastar
  10.                              a.k.a.
  11.                          MRI / Doomsday
  12.                         mri@penti.sit.fi
  13.  
  14.                  8 Jul. 1996  Jakobstad, Finland
  15.                    19 Jun. 1996  Espoo, Finland
  16.  
  17.            Read this today, it might be obsolete tomorrow.
  18.  
  19.   Feel free to upload this document to wherever you find appropriate,
  20.       as long as you keep it in it's original, unmodified form.
  21.     This is free information, you may not charge anything for it.
  22.  
  23.  
  24.  
  25. Table of contents
  26. -----------------
  27.  
  28. 1.  About this document
  29. 2.  Disclaimer
  30. 3.  Definition of terms
  31. 4.  Assume the following
  32. 5.  The slow method
  33. 6.  A faster method
  34. 7.  General structure of the texture mapping function
  35. 8.  Equations for the constant deltas
  36. 9.  Traditional inner loops
  37. 10. Memories from the past
  38. 11. Selfmodifying code
  39. 12. Unrolled and selfmodifying inner loops
  40. 13. Table lookup inner loops
  41. 14. Problems with precalculated runs
  42. 15. Pre-stepping texture coordinates
  43. 16. Special case code
  44. 17. Clipping
  45. 18. Clipping using matrices
  46. 19. Writing a byte, word, dword and other weird things
  47. 20. The data cache
  48. 21. The code cache
  49. 22. Some pairing rules
  50. 23. Pipeline delays
  51. 24. The time stamp counter
  52. 25. Branch prediction
  53. 26. Reference
  54. 27. Where to go from here
  55. 28. Credits and greetings
  56.  
  57.  
  58.  
  59. 1.  About this document
  60. -----------------------
  61.  
  62. This document tries to describe how to make fast affine texture mapping. The
  63. document describes both the general structure as well as the more critical
  64. parts such as inner loops. The information is aimed at both beginners and
  65. also at people who maybe already have a working texture mapper but are
  66. looking for more speed. The goal was to make a good document that would be
  67. useful today, not already be obsolete. So I'm giving you the best information
  68. I can possibly come up with.
  69.  
  70. You don't get the information for free though. You will have to invest some
  71. of your own effort and actually learn what's going on in the inner loops and
  72. select the parts that will be most suitable for you.
  73.  
  74. The information is based on my own work and findings but also on information
  75. found on the net, especially articles posted to the newsgroup
  76. comp.graphics.algorithms and on ideas given to me by other coders. IRC
  77. channel #coders is usually a good place to get new ideas and help. Many of
  78. the coders there are willing to share ideas and answer decent questions.
  79.  
  80. I am not claiming that the methods described here are THE fastest methods of
  81. doing texture mapping. But these methods are what coders are using today and
  82. they ARE fast.
  83.  
  84. To get the most out of this document you should have a good understanding of
  85. 386+ Assembly and C. The asm code and optimizations are aimed especially
  86. for the Intel Pentium CPU.
  87.  
  88. Note that the C code given is only meant as some sort of pseudo code. C is
  89. most of the time much easier to read that asm. For your information I have
  90. the whole texture mapping function in asm. This is overkill, I know, but this
  91. way I get full control over the optimization. In C I can only _hope_ that the
  92. compiler makes the best code possible. I'm certain that a human brain still
  93. is better to optimize code than a compiler. I do not say this because I'm a
  94. true asm-freak. In fact, I had programmed C for a year before even
  95. considering learning asm.
  96.  
  97. I should say that I do not have a masters degree in computer graphics. I'm
  98. merely a 24 year old computer and telecom engineer (B.Sc.) that found
  99. interest in this area. I have never taken any computer graphics related
  100. course in school so if you think I misuses some expressions or terms, or even
  101. leave out some expressions or terms where I should use them, you might very
  102. well be right and I wrong.
  103.  
  104. Also I have to confess that I haven't read Chris Hecker's articles in Game
  105. Developer magazine (http://www.gdmag.com). People tell me that they are good.
  106. You should probably take a look at them also.
  107.  
  108.  
  109.  
  110. 2.  Disclaimer
  111. --------------
  112.  
  113. Some parts of the technical discussion at the end of the document might not
  114. be 100% accurate as of the actual hardware in the Pentium. But from a
  115. programmers point of view the guidelines given should apply anyway.
  116.  
  117. When I state that a inner loop is e.g. 5 clock ticks per pixel, this don't
  118. mean that it will actually run at 5 clock ticks. This is just a theoretical
  119. minimum when I assume that the instructions pair as expected and there are
  120. no cache misses and no delays writing to RAM.
  121.  
  122.  
  123.  
  124. 3.  Definition of terms
  125. -----------------------
  126.  
  127. Just so there won't be any confusion:
  128.  
  129. triangle side     Each triangle has two sides, the left side and the right
  130.                   side.
  131.  
  132. triangle edge     These makes up the outline of the triangle. Usually one
  133.                   interpolates variables along the triangle edges, both on
  134.                   the left and the right side of the triangle.
  135.  
  136. triangle section  A triangle is always made up of 3 sections. These are
  137.                   straight lines which makes up the triangle edges. When
  138.                   interpolating along the triangle edges we must calculate
  139.                   deltas for each of the 3 sections.
  140.  
  141. triangle x        The current x value of a triangle edge on the screen. There
  142.                   are two triangle x, one on the left side and one on the
  143.                   right side of the triangle. Between these is the current
  144.                   scanline.
  145.  
  146. u and v           The x and y components in the bitmap.
  147.  
  148. dudx and dvdx     Our constant deltas for u and v, du/dx and dv/dx. (constant
  149.                   texture gradients for u and v)
  150.  
  151.  
  152.  
  153. 4.  Assume the following
  154. ------------------------
  155.  
  156. We are only drawing triangles. (This is no problem to me as 3D Studio only
  157. uses triangles anyway.) Well actually it doesn't have to be triangles, this
  158. also works on other types of polygons as long as the texture gradients are
  159. constant for the whole polygon surface.
  160.  
  161. You agree that a fractional part of 8 bit is enough for interpolating u and v
  162. on the scanlines of the triangle. Well actually a 16 bit fractional part is
  163. better but inner loops are usually much simpler to do if we only use 8 bits.
  164.  
  165. Bitmaps always has a width of 256 pixels and a maximum height of 256 pixels.
  166. In some of the inner loops we must also assume that the bitmaps are aligned
  167. on 64k.
  168.  
  169. The CPU is a Pentium and we are in 32 bit protected mode and flat memory
  170. model (TASM+WATCOM+PMODE/W).
  171.  
  172.  
  173.  
  174. 5.  The slow method
  175. -------------------
  176.  
  177. The slow method of doing texture mapping is to interpolate u and v (and
  178. triangle x) on both the left and right side of the triangle and then
  179. calculate du/dx and dv/dx for each scanline. Then interpolate u and v when
  180. drawing the scanline. To make this even slower you could first interpolate
  181. the u and v (and triangle x) on both sides of the triangle and store the
  182. values in a edge buffer. Then pick the values from the edge buffer and draw
  183. each scanline.
  184.  
  185.  
  186.  
  187. 6.  A faster method
  188. -------------------
  189.  
  190. Don't use a edge buffer as described in the slow method above. Calculate the
  191. edge deltas when you need them and interpolate along the edges at the same
  192. time you draw each scanline. It's just as simple to do it this way and a lot
  193. faster.
  194.  
  195. One important thing you should realize is that when texture mapping a
  196. triangle (or any type of polygon that has constant texture gradients), you
  197. are interpolating two variables, u and v, whose deltas are constant over the
  198. whole triangle. I repeat, the deltas are constant for the whole triangle.
  199. Make sure you understand this because this is the key to fast texture mapping
  200. (or any other type of linear shading for that matter). I guess that the
  201. correct term isn't constant deltas, rather constant gradients, but I like the
  202. term delta better.
  203.  
  204. Because the deltas (delta u and delta v) are constant, we only need to
  205. calculate them once for the whole triangle. No need to calculate them for
  206. each scanline. Also when interpolating u and v along the edges of the
  207. triangle you only need to interpolate u and v on one side of the triangle.
  208. Triangle x must be interpolated on both sides.
  209.  
  210.  
  211.  
  212. 7.  General structure of the texture mapping function
  213. -----------------------------------------------------
  214.  
  215. Here is the general structure of my texture mapping function. If you have
  216. Watcom C/C++ you can compile it as is. Just initialize VGA mode 0x13 and call
  217. it. I didn't want to include the clipping code as it only would make it more
  218. difficult to read. No kind of pre-stepping or any other type of compensation
  219. is presented here, this is just the bare bones of the function. It might look
  220. big (?) but it is pretty damn simple and efficient if I may say so myself.
  221.  
  222. You should call the function by passing a pointer to an array of 3 vertex
  223. structures and a pointer to the bitmap.
  224.  
  225.     extern char myimage[];  // 256x256 256 color bitmap
  226.     vertex array[3];
  227.     // fill in the values for each vertex in the array here
  228.     DrawTextureTriangle(array, myimage);
  229.  
  230. Note that the function doesn't move the vertex data to some local variables,
  231. it uses pointers to each of the structures instead. This makes it extremely
  232. simple to later on add more variables in the vertex structure which you will
  233. be doing in the case of an environment-bump or Phong-texture-bump mapper.
  234. The same function structure can still be used, just add a few variables to
  235. the vertex structure, calculate 2 more deltas, interpolate 2 more variables
  236. along the left side and make a new inner loop.
  237.  
  238.  
  239. // This is the only Watcom C/C++ specific part of the function. These
  240. // instructions take a 26:6 bit fixed point number and converts it
  241. // to 32:32 bit. Then divides it with another 16:16 bit fixed point
  242. // number. The result is 16:16 bit. This must be done in asm where we
  243. // can do 64/32 bit divides.
  244.  
  245. int shl10idiv(int x, int y);
  246. #pragma aux shl10idiv = \
  247.     " mov   edx, eax "\
  248.     " shl   eax, 10  "\
  249.     " sar   edx, 22  "\
  250.     " idiv  ebx      "\
  251.     parm [eax] [ebx] \
  252.     modify exact [eax edx] \
  253.     value [eax]
  254.  
  255. // sizeof(int) is 4
  256.  
  257. struct vertex
  258. {
  259.     int x,y;    // screen coordinates (integers)
  260.     int u,v;    // vertex u,v (26:6 bit fixed point)
  261. };
  262.  
  263. static vertex * left_array[3], * right_array[3];
  264. static int left_section, right_section;
  265. static int left_section_height, right_section_height;
  266. static int dudx, dvdx;
  267. static int left_u, delta_left_u, left_v, delta_left_v;
  268. static int left_x, delta_left_x, right_x, delta_right_x;
  269.  
  270.  
  271. inline int RightSection(void)
  272. {
  273.     vertex * v1 = right_array[ right_section ];
  274.     vertex * v2 = right_array[ right_section-1 ];
  275.  
  276.     int height = v2->y - v1->y;
  277.     if(height == 0)
  278.         return 0;
  279.  
  280.     // Calculate the deltas along this section
  281.  
  282.     delta_right_x = ((v2->x - v1->x) << 16) / height;
  283.     right_x = v1->x << 16;
  284.  
  285.     right_section_height = height;
  286.     return height;                  // return the height of this section
  287. }
  288.  
  289. inline int LeftSection(void)
  290. {
  291.     vertex * v1 = left_array[ left_section ];
  292.     vertex * v2 = left_array[ left_section-1 ];
  293.  
  294.     int height = v2->y - v1->y;
  295.     if(height == 0)
  296.         return 0;
  297.  
  298.     // Calculate the deltas along this section
  299.  
  300.     delta_left_x = ((v2->x - v1->x) << 16) / height;
  301.     left_x = v1->x << 16;
  302.     delta_left_u = ((v2->u - v1->u) << 10) / height;
  303.     left_u = v1->u << 10;
  304.     delta_left_v = ((v2->v - v1->v) << 10) / height;
  305.     left_v = v1->v << 10;
  306.  
  307.     left_section_height = height;
  308.     return height;                  // return the height of this section
  309. }
  310.  
  311. void DrawTextureTriangle(vertex * vtx, char * bitmap)
  312. {
  313.     vertex * v1 = vtx;
  314.     vertex * v2 = vtx+1;
  315.     vertex * v3 = vtx+2;
  316.  
  317.     // Sort the triangle so that v1 points to the topmost, v2 to the
  318.     // middle and v3 to the bottom vertex.
  319.  
  320.     if(v1->y > v2->y) { vertex * v = v1; v1 = v2; v2 = v; }
  321.     if(v1->y > v3->y) { vertex * v = v1; v1 = v3; v3 = v; }
  322.     if(v2->y > v3->y) { vertex * v = v2; v2 = v3; v3 = v; }
  323.  
  324.     // We start out by calculating the length of the longest scanline.
  325.  
  326.     int height = v3->y - v1->y;
  327.     if(height == 0)
  328.         return;
  329.     int temp = ((v2->y - v1->y) << 16) / height;
  330.     int longest = temp * (v3->x - v1->x) + ((v1->x - v2->x) << 16);
  331.     if(longest == 0)
  332.         return;
  333.  
  334.     // Now that we have the length of the longest scanline we can use that
  335.     // to tell us which is left and which is the right side of the triangle.
  336.  
  337.     if(longest < 0)
  338.     {
  339.         // If longest is neg. we have the middle vertex on the right side.
  340.         // Store the pointers for the right and left edge of the triangle.
  341.         right_array[0] = v3;
  342.         right_array[1] = v2;
  343.         right_array[2] = v1;
  344.         right_section  = 2;
  345.         left_array[0]  = v3;
  346.         left_array[1]  = v1;
  347.         left_section   = 1;
  348.  
  349.         // Calculate initial left and right parameters
  350.         if(LeftSection() <= 0)
  351.             return;
  352.         if(RightSection() <= 0)
  353.         {
  354.             // The first right section had zero height. Use the next section.
  355.             right_section--;
  356.             if(RightSection() <= 0)
  357.                 return;
  358.         }
  359.  
  360.         // Ugly compensation so that the dudx,dvdx divides won't overflow
  361.         // if the longest scanline is very short.
  362.         if(longest > -0x1000)
  363.             longest = -0x1000;
  364.     }
  365.     else
  366.     {
  367.         // If longest is pos. we have the middle vertex on the left side.
  368.         // Store the pointers for the left and right edge of the triangle.
  369.         left_array[0]  = v3;
  370.         left_array[1]  = v2;
  371.         left_array[2]  = v1;
  372.         left_section   = 2;
  373.         right_array[0] = v3;
  374.         right_array[1] = v1;
  375.         right_section  = 1;
  376.  
  377.         // Calculate initial right and left parameters
  378.         if(RightSection() <= 0)
  379.             return;
  380.         if(LeftSection() <= 0)
  381.         {
  382.             // The first left section had zero height. Use the next section.
  383.             left_section--;
  384.             if(LeftSection() <= 0)
  385.                 return;
  386.         }
  387.  
  388.         // Ugly compensation so that the dudx,dvdx divides won't overflow
  389.         // if the longest scanline is very short.
  390.         if(longest < 0x1000)
  391.             longest = 0x1000;
  392.     }
  393.  
  394.     // Now we calculate the constant deltas for u and v (dudx, dvdx)
  395.  
  396.     int dudx = shl10idiv(temp*(v3->u - v1->u)+((v1->u - v2->u)<<16),longest);
  397.     int dvdx = shl10idiv(temp*(v3->v - v1->v)+((v1->v - v2->v)<<16),longest);
  398.  
  399.     char * destptr = (char *) (v1->y * 320 + 0xa0000);
  400.  
  401.     // If you are using a table lookup inner loop you should setup the
  402.     // lookup table here.
  403.  
  404.     // Here starts the outer loop (for each scanline)
  405.  
  406.     for(;;)
  407.     {
  408.         int x1 = left_x >> 16;
  409.         int width = (right_x >> 16) - x1;
  410.  
  411.         if(width > 0)
  412.         {
  413.             // This is the inner loop setup and the actual inner loop.
  414.             // If you keep everything else in C that's up to you but at
  415.             // least remove this inner loop in C and insert some of
  416.             // the Assembly versions.
  417.  
  418.             char * dest = destptr + x1;
  419.             int u  = left_u >> 8;
  420.             int v  = left_v >> 8;
  421.             int du = dudx   >> 8;
  422.             int dv = dvdx   >> 8;
  423.  
  424.             // Watcom C/C++ 10.0 can't get this inner loop any tighter
  425.             // than about 10-12 clock ticks.
  426.  
  427.             do
  428.             {
  429.                 *dest++ = bitmap[ (v & 0xff00) + ((u & 0xff00) >> 8) ];
  430.                 u += du;
  431.                 v += dv;
  432.             }
  433.             while(--width);
  434.         }
  435.  
  436.         destptr += 320;
  437.  
  438.         // Interpolate along the left edge of the triangle
  439.         if(--left_section_height <= 0)  // At the bottom of this section?
  440.         {
  441.             if(--left_section <= 0)     // All sections done?
  442.                 return;
  443.             if(LeftSection() <= 0)      // Nope, do the last section
  444.                 return;
  445.         }
  446.         else
  447.         {
  448.             left_x += delta_left_x;
  449.             left_u += delta_left_u;
  450.             left_v += delta_left_v;
  451.         }
  452.  
  453.         // Interpolate along the right edge of the triangle
  454.         if(--right_section_height <= 0) // At the bottom of this section?
  455.         {
  456.             if(--right_section <= 0)    // All sections done?
  457.                 return;
  458.             if(RightSection() <= 0)     // Nope, do the last section
  459.                 return;
  460.         }
  461.         else
  462.         {
  463.             right_x += delta_right_x;
  464.         }
  465.     }
  466. }
  467.  
  468.  
  469.  
  470. 8.  Equations for the constant deltas
  471. -------------------------------------
  472.  
  473. Sort the vertices in the triangle so that the topmost vertex is known as
  474. x1,y1 and the bottom vertex is known as x3,y3. Like the drawing below.
  475.  
  476.                                x1,y1
  477.                                 p1
  478.                                   /
  479.                                / /
  480.                             /   /
  481.                          /     /
  482.                       /       /
  483.                    /         /
  484.         x2,y2   /           /
  485.         p2   /_____________/
  486.              \    width   /
  487.                \         /
  488.                  \      /
  489.                    \   /
  490.                      \/
  491.                    x3,y3
  492.                     p3
  493.  
  494.   xn,yn     - x,y screen coordinates at vertex n (integers)
  495.   pn        - Value of variable at vertex n to calculate the constant delta
  496.               for. Note that this variable is assumed to have a 6 bit
  497.               fractional part (26:6 bit fixed point).
  498.   width     - Width of the longest scanline in the triangle
  499.  
  500.  
  501. The reason why I have p as a 26:6 bit fixed point and not 16:16 or 24:8 bit
  502. fixed point is just for being able to store u and v with a little higher
  503. precision in the 3D structure and still use only words to save space.
  504.  
  505. Sorting 3 vertices is no more that 3 compares. Another thing: Don't load
  506. all x,y,u and v values of the vertices into registers. Use pointers to the
  507. vertex structures instead. This will also make it easier when you later on
  508. implement your Phong-texture-bump mapper. Something like this:
  509.  
  510.     ; EDX -> vertex 1
  511.     ; ESI -> vertex 2
  512.     ; EDI -> vertex 3
  513.     mov     EAX, [EDX+vertex_y]
  514.     cmp     EAX, [ESI+vertex_y]
  515.     jle     short @@sorta
  516.     xchg    EDX, ESI                ; swap v1 - v2
  517.  @@sorta:
  518.     mov     EAX, [EDX+vertex_y]
  519.     cmp     EAX, [EDI+vertex_y]
  520.     jle     short @@sortb
  521.     xchg    EDX, EDI                ; swap v1 - v3
  522.  @@sortb:
  523.     mov     EAX, [ESI+vertex_y]
  524.     cmp     EAX, [EDI+vertex_y]
  525.     jle     short @@sortc
  526.     xchg    ESI, EDI                ; swap v2 - v3
  527.  @@sortc:
  528.     ; EDX -> topmost vertex
  529.     ; ESI -> middle vertex
  530.     ; EDI -> bottom vertex
  531.  
  532.  
  533. The following two equations needs only be calculated once for all the
  534. constant deltas in the triangle. Skip the triangle if y3 == y1, i.e. if the
  535. triangle has zero height. The width can be either positive or negative
  536. depending on which side the x2,y2 vertex is. This will be useful information
  537. when sorting out which is left and which is the right side of the triangle.
  538.  
  539.               (y2-y1) << 16
  540.        temp = --------------
  541.                   y3-y1
  542.  
  543.        width = temp * (x3-x1) + ((x1-x2) << 16)
  544.  
  545. This will give you temp and width as 16:16 bit fixed point.
  546.  
  547. The equation below is used to calculate the delta for a variable that should
  548. be interpolated over the triangle, e.g. texture u. Beware of the denominator
  549. in this equation! Make sure it won't cause divide overflow in case the width
  550. is less than one pixel. (Remember that width is a 16:16 bit fixed point
  551. number.) Note that shift by 10 in the equation. This is because p1,p2,p3 has
  552. a 6 bit fractional part. The resulting delta p is a 16:16 bit number. Note
  553. that this divide should be done in asm where we can do 64/32 bit divides.
  554.  
  555.                   ( temp * (p3-p1) + ((p1-p2) << 16) ) << 10
  556.        delta p = --------------------------------------------
  557.                                  width
  558.  
  559. So for a texture mapper where we have 2 variables (u,v) to interpolate over
  560. the triangle, we have a total of 3 divs and 3 muls to calculate dudx and
  561. dvdx.
  562.  
  563.  
  564. Here is another equation that can be used to calculate the deltas with. It
  565. was posted to the newsgroup comp.graphic.algorithm by Mark Pursey.
  566.  
  567.   There is a cleaner way, which doesn't rely on finding the widest line:
  568.   A-B-C: a triangle with screen x and y components, as well as t, a
  569.   value which could represent lightning, texture coordinates etc.
  570.   The following equation gives you the increment for t per horizontal pixel:
  571.  
  572.           (At-Ct)*(By-Cy) - (Bt-Ct)*(Ay-Cy)
  573.   dt/dx = ---------------------------------
  574.           (Ax-Cx)*(By-Cy) - (Bx-Cx)*(Ay-Cy)
  575.  
  576. I've been told that this is the correct way to calculate the deltas (or
  577. constant texture gradients). This might very well be true but the other
  578. equations gives me good results and the length of the longest scanline for
  579. free. In this equation the denominator is reusable for both u and v. This
  580. makes a total of 6 muls and 2 divs. Remember to add the necessary shifts if
  581. you do this in fixed point.
  582.  
  583.  
  584.  
  585. 9.  Traditional inner loops
  586. ---------------------------
  587.  
  588. So assuming you have come so far that you have the triangle sorted, the
  589. constant deltas calculated, the u and v deltas on the left side calculated,
  590. deltas for triangle x calculated for both sides, and you are actually
  591. interpolating those values for each scanline, we come to the very core of the
  592. texture mapper, the inner loop. I'll first present a few traditional inner
  593. loops that interpolates u and v while plotting the scanline. These loops are
  594. simple, fast and works very well.
  595.  
  596. The loops assume the following:
  597.  
  598.  ebx     = ptr to bitmap aligned on 64k. (the low 16 bits zero)
  599.  edi     = ptr to first destination pixel to plot in this scanline
  600.  ebp     = width of scanline (loop counter)
  601.  left_u  = current u on the left edge of the triangle (16:16 bit fixed point)
  602.  left_v  = current v on the left edge of the triangle (16:16 bit fixed point)
  603.  du      = our constant delta u (24:8 bit fixed point)
  604.  dv      = our constant delta v (24:8 bit fixed point)
  605.  
  606.  
  607. The first loop interpolates the u and v in two 32 bit registers (ecx, edx).
  608. We are one register short here so we use the dudx variable directly in the
  609. inner loop. This loop should run at 6 ticks per pixel. eax is not used for
  610. anything else than holding the pixel so we could unroll this loop to plot
  611. a word or dword at a time.
  612.  
  613.    mov   ecx, [left_u]              ; current u
  614.    mov   edx, [left_v]              ; current u
  615.    shr   ecx, 8                     ; make them 28:8 bit fixed point
  616.    shr   edx, 8
  617.    mov   bl, ch                     ; make ebx point to the first textel
  618.    mov   bh, dh
  619.    mov   esi, [du]
  620.  
  621.  @@inner:
  622.     add   edx, [dv]                 ; update v
  623.     add   ecx, esi                  ; update u
  624.     mov   al, [ebx]                 ; get pixel from aligned texture map
  625.     mov   bl, ch
  626.     mov   [edi], al                 ; plot pixel
  627.     mov   bh, dh
  628.     inc   edi
  629.     dec   ebp
  630.     jnz   @@inner
  631.  
  632.  
  633. Just to show that it is also possible to directly interpolate u and v in ebx
  634. I'll present this one that uses the carry flag to add the "overflow" from the
  635. fractional part to the whole part of u and v.
  636.  
  637.     mov   cl, byte ptr [left_u+1]   ; fractional part of current u
  638.     mov   ch, byte ptr [left_v+1]   ; fractional part of current v
  639.     mov   dl, byte ptr [du]         ; fractional part of delta u
  640.     mov   dh, byte ptr [dv]         ; fractional part of delta v
  641.     mov   bl, byte ptr [left_u+2]   ; whole part of current u
  642.     mov   bh, byte ptr [left_v+2]   ; whole part of current v
  643.  
  644.  @@inner:
  645.     mov   al, [ebx]                 ; get pixel from aligned texture map
  646.     add   cl, dl                    ; update fractional part of u
  647.     adc   bl, byte ptr [du+1]       ; + whole part of dudx (+carry)
  648.     add   ch, dh                    ; update fractional part of v
  649.     adc   bh, byte ptr [dv+1]       ; + whole part of dvdx (+carry)
  650.     mov   [edi], al                 ; plot pixel
  651.     inc   edi
  652.     dec   ebp
  653.     jnz   @@inner
  654.  
  655.  
  656. The following loop uses a combination of interpolation in one 32 bit register
  657. (ecx) and the carry overflow method. We have just enough registers in this
  658. loop that we don't need to use any memory variables. On the other hand this
  659. makes it impossible to unroll it and plot a word or dword at a time. Anyway,
  660. this version should run at 5 ticks per pixel.
  661.  
  662.     mov   ecx, [left_u]
  663.     shr   ecx, 8                    ; make it 28:8 bit fixed point
  664.     mov   esi, [du]
  665.     mov   dl, byte ptr [dv]         ; fractional part of delta v
  666.     mov   dh, byte ptr [left_v+1]   ; fractional part of current v
  667.     mov   ah, byte ptr [dv+1]       ; whole part of delta v
  668.     mov   bh, byte ptr [left_v+2]   ; whole part of current v
  669.     mov   bl, ch
  670.  
  671.  @@inner:
  672.     add   ecx, esi                  ; update u
  673.     mov   al, [ebx]                 ; get pixel from aligned texture map
  674.     mov   bl, ch
  675.     add   dh, dl                    ; update fractional part of v
  676.     adc   bh, ah                    ; + whole part of of delta v (+carry)
  677.     mov   [edi], al                 ; plot pixel
  678.     inc   edi
  679.     dec   ebp
  680.     jnz   @@inner
  681.  
  682. The loop counter (ebp) in the above loop can be removed if we reorder the
  683. registers a bit and plot the scanline from right to left.
  684.  
  685.  @@inner:
  686.     add   ecx, ebp
  687.     mov   al, [ebx]
  688.     mov   bl, ch
  689.     add   dh, dl
  690.     adc   dh, ah
  691.     mov   [edi+esi], al
  692.     dec   esi
  693.     jnz   @@inner
  694.  
  695. The loop should now run at 4 clock ticks.
  696.  
  697. I'm sure there are other ways to make these kind of loops but this is what I
  698. could come up with.
  699.  
  700. After I wrote the above sentence, there was a post in the newsgroup
  701. comp.graphics.algorithms by Sean L. Palmer where he presented the following
  702. 4 tick loop:
  703.  
  704.     Texture must be aligned on a 64K boundary. Must be 256x256.
  705.     Only 8 bits used for fractions, means shaky textures.
  706.     Start at right end of scanline
  707.  
  708.     T=texture adr
  709.     D=dest adr+count (start)
  710.     E=dest adr (end)
  711.     X=tex X int          (whole part of initial u)
  712.     x=tex X frac         (fractional part of initial u)
  713.     Y=tex Y int          (whole part of initial v)
  714.     y=tex Y frac         (fractional part of initial v)
  715.     H=tex X step int     (whole part of delta u)
  716.     h=tex X step frac    (fractional part of delta u)
  717.     V=tex Y step int     (whole part of delta v)
  718.     v=tex Y step frac    (fractional part of delta v)
  719.     m=account for borrow for negative Y step, either 0 or 0FFh
  720.     p=texture pixel
  721.  
  722.     edi=DDDD
  723.     esi=EEEE
  724.     edx=TTYX
  725.     eax=000p
  726.     ebx=x0Yy
  727.     ecx=hmVv
  728.     ebp=000H
  729.     esp=
  730.  
  731.       mov   dh,bh
  732.     @@L:
  733.       mov   al,[edx]
  734.       add   ebx,ecx
  735.       adc   edx,ebp
  736.       dec   edi
  737.       mov   dh,bh
  738.       cmp   edi,esi
  739.       mov   [edi],al
  740.       jne   @@L
  741.  
  742. It's not necessary to simulate the loop counter this way. esi is not really
  743. used in the loop so we might as well use it as a loop counter and draw the
  744. scanline from left to right (the way I like to draw my scanlines). Like this:
  745.  
  746.   @@inner:
  747.     mov   al, [edx]
  748.     add   ebx, ecx
  749.     adc   edx, ebp
  750.     inc   edi
  751.     mov   dh, bh
  752.     dec   esi
  753.     mov   [edi], al
  754.     jnz   @@inner
  755.  
  756. Both of these loops uses eax only to hold the pixel so they can be unrolled
  757. to plot a word or dword at a time. In fact, by unrolling this loop to plot
  758. a dword per turn it might very well beat the table lookup inner loop
  759. presented below. By unrolling this loop we can remove 3 instructions,
  760. "inc edi", "dec esi" and "jnz @@inner". This will also mean that the loop
  761. will become too tight that will lead to AGI delays instead.
  762.  
  763.  
  764.  
  765. 10. Memories from the past
  766. --------------------------
  767.  
  768. I as many others, started coding asm in real mode and later on moved to
  769. protected mode and flat model. The thing I miss about real mode was the
  770. ability to have a pointer in the low 16 bit and a variable in the high 16 bit
  771. of a 32 bit register. In flat model we need all 32 bits for the pointer.
  772. Sure, one can setup a selector and address the data with only the low 16 bits
  773. but all prefix bytes can be seen as a 1 clock tick, nonpairable instruction
  774. on the Pentium. So addressing with only 16 bit and using a segment override
  775. will give 2 prefix bytes or 2 ticks delay.
  776.  
  777. The following loop in real mode was for a bitmap scaler I once used. We have
  778. 4 variables in only 2 registers (edi, ebx).
  779.  
  780.     ; ebx = neg(loop counter)   : source ptr
  781.     ; edi = decision variable   : destination pointer
  782.     ; ecx = frac. part of delta : 1
  783.     ; edx = 1                   : whole part of delta
  784.     ; the delta is 16:16 bit
  785.  @@inner:
  786.     mov   al, [bx]
  787.     mov   es:[di], al
  788.     add   edi, ecx      ; update fractional part : move dest. pointer
  789.     adc   ebx, edx      ; update loop counter    : whole step in bmp (+carry)
  790.     jnc   @@inner       ; jump if loop counter didn't overflow
  791.  
  792. OK, this loop is crap on a Pentium but ain't it pretty? Just two adds to move
  793. both pointers, update the decision variable and loop counter. If we only had
  794. 64 bit registers on the Pentium...
  795.  
  796.  
  797.  
  798. 11. Selfmodifying code
  799. -----------------------
  800.  
  801. One way to get rid of the memory variables in inner loops is to use
  802. selfmodifying code. When you have calculated a constant delta and are about
  803. to store it in a memory variable, why don't you store it right into a
  804. instruction as a constant in the inner loop? It's just as simple. Just
  805. remember to not use CS as segment override as we are in protected mode.
  806.  
  807. I must warn you about this way of coding, especially on the Pentium (read
  808. about the code cache at the end). It can actually make the loop slower even
  809. if you think you cut away a few ticks.
  810.  
  811. Doing more complex shadings like environment-bump or Phong-texture-bump,
  812. selfmodifying code might be the only way to get it to run at all. I.e. not
  813. having to write to any memory variables from the inner loop. If you are about
  814. to make your loop selfmodifying, compare it with your old loop by actually
  815. timing a typical scene. Then you'll know if you gained anything.
  816.  
  817. If your loop is faster with selfmodifying code and the environment your
  818. application is aimed for allows selfmodifying code, I'd definitely say go for
  819. it, use selfmodifying code.
  820.  
  821.  
  822.  
  823. 12. Unrolled and selfmodifying inner loops
  824. ------------------------------------------
  825.  
  826. I don't really see these as an alternative to the traditional inner loops on
  827. the Pentium. I present them here just because they are interesting.
  828.  
  829. The deltas are constant so the offsets for each pixel in each scanline into
  830. the bitmap will also be constant. I.e. we can precalculate a whole run and
  831. use that in the inner loop. The inner loops for these type of texture mappers
  832. can look very different. The most radical must be to unroll it all the way
  833. and to plug in the offsets right into the mov instructions, i.e.
  834. selfmodifying code. These completely unrolled loops will be pretty big also.
  835. The loop below is 14 byte per pixel which means over 4k code for a whole 320
  836. pixel scanline. The loop will take up half of the code cache. Ouch! (read
  837. about the code cache at the end). Here is some code that shows the principle
  838. of this type of "inner loop":
  839.  
  840.     jmp   ecx                   ; Jump to the right place in the "loop"
  841.     mov   al, [esi+12345]
  842.     mov   [edi+319], al
  843.     mov   al, [esi+12345]       ; Get pixel
  844.     mov   [edi+318], al         ; Plot pixel
  845.     ......
  846.     mov   al, [esi+12345]       ; '12345' is the selfmodifying part
  847.     mov   [edi+2], al           ; that will be modified once per triangle
  848.     mov   al, [esi+12345]
  849.     mov   [edi+1], al
  850.     mov   al, [esi+12345]
  851.     mov   [edi+0], al
  852.  
  853. Note that we are doing it backwards, from right to left. This makes it easier
  854. to setup esi and edi. As the code for each pixel in this loop is 14 byte you
  855. will be doing a X*14 when calculating the jump offset. X*14 is (X<<4)-X-X.
  856. You should of coarse not plug in the offsets for the whole loop if you only
  857. have a small triangle. The length of the longest scanline is a byproduct from
  858. the constant delta calculations.
  859.  
  860.  
  861. So what about the 1.5 tick per pixel loop?
  862. Well the following peace of code is usually what people think of. I'm not
  863. really sure that this is actually 1.5 tick per pixel as the 'mov [edi+?],ax'
  864. has a operand size prefix byte. This code will need some work to make the
  865. instructions pair on the Pentium. Of coarse this loop also suffers from the
  866. same problems as the previous selfmodifying, unrolled loop.
  867.  
  868.     jmp   ecx
  869.     ......
  870.     mov   al, [esi+12345]
  871.     mov   ah, [esi+12345]
  872.     mov   [edi+4], ax
  873.     mov   al, [esi+12345]
  874.     mov   ah, [esi+12345]
  875.     mov   [edi+2], ax
  876.     mov   al, [esi+12345]
  877.     mov   ah, [esi+12345]
  878.     mov   [edi], ax
  879.  
  880.  
  881.  
  882. 13. Table lookup inner loops
  883. ----------------------------
  884.  
  885. Now to a cooler method that is not selfmodifying and don't need to be
  886. unrolled all the way. The idea is very similar to the unrolled loops above
  887. but in this loop we have the offsets stored in a lookup table instead. For
  888. each pixel we get the address of the next pixel from the lookup table. This
  889. method should be much more Pentium friendly. Also this inner loop don't need
  890. to have the bitmap aligned on 64k as the traditional inner loops.
  891.  
  892. The loop assume the following:
  893.  
  894.  esi     = ptr to bitmap (no alignment needed)
  895.  edi     = ptr to first destination pixel to plot in this scanline
  896.  ebp     = width of scanline (loop counter)
  897.  left_u  = current u on the left edge of the triangle (16:16 bit fixed point)
  898.  left_v  = current v on the left edge of the triangle (16:16 bit fixed point)
  899.  lookup  = ptr to the precalculated lookup table. The lookup table is an
  900.            array of dwords.
  901.  
  902.  
  903.     mov   edx, [lookup]
  904.     xor   eax, eax
  905.     mov   al, byte ptr [left_u+2]
  906.     mov   ah, byte ptr [left_v+2]
  907.     add   esi, eax
  908.  
  909.   @@inner:
  910.     mov   al, [esi+ebx]         ; Get pixel
  911.     mov   ebx, [edx]            ; Get offset for next pixel
  912.     mov   [edi], al             ; Plot pixel
  913.     add   edx, 4
  914.     inc   edi
  915.     dec   ebp
  916.     jnz   @@inner
  917.  
  918.  
  919. The same loop could look like this in C:
  920.  
  921.     // destptr = ptr to screen + y*320
  922.     // bitmap  = ptr to bitmap
  923.     // lookup  = ptr to lookup table
  924.     // x1      = start screen x coordinate of scanline
  925.     // width   = width of scanline
  926.  
  927.     char * dest = destptr + x1;
  928.     char * src  = bitmap + (left_u>>16) + (left_v>>16)*256;
  929.  
  930.     for(; width--; )
  931.     {
  932.         *(dest++) = src[ *(lookup++) ];
  933.     }
  934.  
  935.  
  936. The above loop in asm should be 4 clock ticks per pixel on a Pentium. This
  937. loop can be changed to plot 4 pixels at a time:
  938.  
  939.   @@inner:
  940.     mov   al, [esi+ebx]         ; Get pixel #1
  941.     mov   ebx, [edx]
  942.     mov   ah, [esi+ecx]         ; Get pixel #2
  943.     mov   ecx, [edx+4]
  944.     shl   eax, 16               ; Move pixels 1 and 2 to the high word
  945.     add   edi, 4
  946.     mov   al, [esi+ebx]         ; Get pixel #3
  947.     mov   ebx, [edx+8]
  948.     mov   ah, [esi+ecx]         ; Get pixel #4
  949.     mov   ecx, [edx+12]
  950.     rol   eax, 16               ; Swap the high and low words
  951.     add   edx, 16
  952.     mov   [edi], eax            ; Plot all 4 pixels
  953.     dec   ebp
  954.     jnz   @@inner
  955.  
  956. Now this loop is 9 (8 if we assume that shl and rol are pairable in the U
  957. pipeline) ticks per 4 pixel with the pixels written as a dword. Very
  958. good if we align the write on dword. Use the other loop for very short lines
  959. or to get this one aligned on dword and use this for the rest of the
  960. scanline.
  961.  
  962.  
  963. Calculate the lookup table with the following loop (this loop can also be
  964. used to calculate the offsets in the selfmodifying example):
  965. (dudx and dvdx are 16:16 bit fixed point. lookup is an array of dwords)
  966.  
  967.    int du = dudx >> 8;
  968.    int dv = dvdx >> 8;
  969.    int u = 0;
  970.    int v = 0;
  971.    for( width of longest scanline )
  972.    {
  973.       *lookup++ = (u>>8) + (v & 0xffffff00);
  974.       u += du;
  975.       v += dv;
  976.    }
  977.  
  978.    ; ebx = ecx = 0
  979.    ; esi = delta u  (26:8 bit fixed point)
  980.    ; edi = delta v  (26:8 bit fixed point)
  981.    ; edx = ptr to lookup table
  982.    ; ebp = length of table (the width of the longest scanline)
  983.  
  984.  @@mklookup:
  985.     mov   eax, ecx
  986.     add   ecx, edi          ; update v
  987.     mov   al, bh
  988.     add   ebx, esi          ; update u
  989.     mov   [edx], eax        ; lookup[edx] = u+256*v
  990.     add   edx, 4
  991.     dec   ebp
  992.     jnz   @@mklookup
  993.  
  994.  
  995.  
  996. 14. Problems with precalculated runs
  997. ------------------------------------
  998.  
  999. The more I play around with inner loops that uses the same precalculated run
  1000. for each scanline, the more skeptic I get. This is because they all suffers
  1001. from the same problem, no matter if we use a lookup table or if we have a
  1002. unrolled selfmodified loop.
  1003.  
  1004. In the case of the lookup table inner loop we always start at the beginning
  1005. of the table when drawing a scanline. This is wrong and will give very bad
  1006. distortion especially when the triangle is zoomed in close. Always starting
  1007. at the beginning of the table is the same as ignoring the fractional parts of
  1008. the initial u and v of the scanline. So to fix this we should start somewhere
  1009. into the table depending on the initial fractional parts of u and v. But this
  1010. is impossible because u and v are interpolated separately on the triangle
  1011. edge but are fixed to each other in the lookup table. Wilco Dijkstra posted
  1012. the following solution in comp.graphics.algorithms:
  1013.  
  1014.  
  1015.     The basic idea is correct. What you mean is using subpixel positioning
  1016.     with one or two bits precision. For example, for 2 bits subpixel
  1017.     positioning you have to create 4 * 4 tables of the longest scanline.
  1018.     The first table starts at u = v = 0, second u = 0, v = 0.25, third u  0,
  1019.     v = 0.50 fourth u = 0, v = 0.75, fifth u = 0.25, v = 0, etc.
  1020.     When stepping down the scanlines, select the table giving the 2 most
  1021.     significant fractional bits of u and v. The maximum error you get is 1/8
  1022.     in each direction (when proper rounding is used!). Thus this is 64 times
  1023.     more precise than using no subpixel positioning.
  1024.  
  1025.     The problem is that it's only faster for very large triangles (eg. more
  1026.     than 32 scanlines deep), so it may be faster (and more accurate) to draw
  1027.     the texture in the standard way, without a table.
  1028.  
  1029.  
  1030. This method will reduce the distortion. On the other hand the lookup tables
  1031. will require much more memory that in turn will push out other cached data,
  1032. not to mention the additional time it takes to setup the tables.
  1033.  
  1034.  
  1035.  
  1036. 15. Pre-stepping texture coordinates
  1037. ------------------------------------
  1038.  
  1039. When we interpolate u, v and triangle x along the left edge of the triangle
  1040. we always truncates triangle x when drawing a scanline. This is natural
  1041. because we can only draw whole pixels. When we truncates x we must also
  1042. adjust the initial u and v of the scanline. Adjusting u and v will give much
  1043. cleaner and stable textures. Note that this only applies if you use a
  1044. traditional inner loop. Don't bother doing this if you are using a table
  1045. lookup inner loop.  Kevin Baca sent me the following explanation:
  1046.  
  1047.  
  1048.     No matter how you compute screen pixels, you need to "pre-step" your
  1049.     texture coordinates by the difference between actual screen  coordinates
  1050.     and screen pixels.  It looks like this:
  1051.  
  1052.     // sp = screen pixel, sc = screen coordinate.
  1053.     float sc, diff, u, v, dudx, dvdx;
  1054.     int sp;
  1055.  
  1056.     sp = (int) sc;
  1057.     diff = sc - (float) sp;
  1058.     u -= dudx * diff;
  1059.     v -= dvdx * diff;
  1060.  
  1061.     You can actually do this without multiplies (by calculating a dda for
  1062.     each edge that determines when to add an extra 1 to the texel
  1063.     coordinates).
  1064.  
  1065.  
  1066.  
  1067. 16. Special case code
  1068. ---------------------
  1069.  
  1070. It often pays off to make special case code that takes care of the edge delta
  1071. calculations when a triangle section is 1, 2 or 4 pixels high. Then you can
  1072. skip the divs and use shifts instead.
  1073.  
  1074. I once made a histogram of the length of each scanline in the very popular
  1075. chrmface.3ds object. This object has about 850 triangles and was scaled up
  1076. so it just touched the top and the bottom of a 320x200 pixel screen. The
  1077. histogram showed that most scanlines was only 1 or 2 pixels wide. This proves
  1078. that the outer loop is just as important as the inner loop and also that it
  1079. might be a good idea to have special case code for those 1 or 2 pixel lines.
  1080.  
  1081. width    number of scanlines
  1082.   1     *********************
  1083.   2     ******************
  1084.   3     **********
  1085.   4     ******
  1086.   5     ***
  1087.   6     **
  1088.   7     **
  1089.  
  1090.  
  1091.  
  1092. 17. Clipping
  1093. ------------
  1094.  
  1095. Clipping is most of the time a real pain in the ass implementing. It will
  1096. always mess up a nice looking routine with extra junk. One possibility is to
  1097. have two separate functions, one with clipping and one with no clipping. Then
  1098. test the triangle if it needs clipping before calling any of the functions.
  1099.  
  1100. The actual clipping code is not that difficult to implement really. Say if
  1101. you need to clip a texture mapped scanline, you first have to get the number
  1102. of pixels you need to skip at the end of the scanline and the number of
  1103. pixels in the beginning of the scanline. Then subtract the number of pixels
  1104. skipped from the original scanline width. If you skipped some pixels at the
  1105. start of the scanline, the new starting u and v must be calculated. This is
  1106. done by multiplying the pixels skipped by delta u and delta v respectively.
  1107. And adding the original starting u and v of coarse.
  1108.  
  1109. The following code is what I'm using to sort out the stuff:
  1110.  
  1111.     movsx   EBP, word ptr [left_x+2]    ; Get the integer part from the
  1112.     movsx   ECX, word ptr [right_x+2]   ; 16:16 bit numbers.
  1113.     mov     EDX, EBP
  1114.     sub     EDX, ECX
  1115.     ; EDX = width of scanline
  1116.     ; ECX = x1
  1117.     ; EBP = x2
  1118.     mov     EBX, EDX
  1119.     sub     EBP, [_RightClip]
  1120.     jle     short @@rightok
  1121.     sub     EDX, EBP                    ; skip pixels at end
  1122.  @@rightok:
  1123.     xor     EAX, EAX
  1124.     cmp     ECX, [_LeftClip]
  1125.     jge     short @@leftok
  1126.     mov     EAX, [_LeftClip]
  1127.     sub     EAX, ECX
  1128.     mov     ECX, [_LeftClip]
  1129.  @@leftok:
  1130.     sub     EDX, EAX                    ; skip pixels at start
  1131.     jle     @@notvisible
  1132.     ; EAX = pixels skipped at start
  1133.     ; ECX = clipped x1
  1134.     ; EDX = clipped width of scanline
  1135.  
  1136. So now you just have to multiply EAX by delta u and add the original u to get
  1137. the clipped u. The same apply for v.
  1138.  
  1139.  
  1140.  
  1141. 18. Clipping using matrices
  1142. ---------------------------
  1143.  
  1144. I've been told that clipping should not be done scanline by scanline in the
  1145. texture mapping function. But I have yet to find a simple alternative
  1146. solution to this. Don't confuse the clipping I'm referring to with removal of
  1147. nonvisible polygons. When we arrive at the texture mapping function we should
  1148. already have removed those triangles that are backface or outside the
  1149. viewcone.
  1150.  
  1151. Kevin Baca sent me the following explanation on how to decide if vertices
  1152. should be clipped or not.
  1153.  
  1154.  
  1155.     If you use homogeneous matrices to do your transformations
  1156.     it's actually very simple to clip before you do the perspective
  1157.     divide to get screen coordinates.
  1158.  
  1159.     Using homogeneous coordinates, you get vertices of the form [X Y Z W]
  1160.     after doing the perspective projection.  To get actual screen
  1161.     coordinates, you divide X and Y by W.  If you are going to
  1162.     "Normalized Device Coordinates" the results of these divisions will
  1163.     be -1 < X' < 1 and -1 < Y' < 1.  Therefore, to do clipping you need
  1164.     to perform the following comparison before the perspective divide:
  1165.  
  1166.     -W < X < W, -W < Y < W.
  1167.  
  1168.     To clip along the Z axis, you can do the same thing, but I usually
  1169.     use the following comparison instead:
  1170.  
  1171.     0 < Z < W.
  1172.  
  1173.     To do a perspective projection, multiply the projection matrix, P, by
  1174.     the view matrix, V:  M = P * V.
  1175.  
  1176.     The view matrix is the result of all your transformations
  1177.     (translations, rotations, scalings, etc.) of both the model and the
  1178.     camera.  For the projection matrix, I use the following:
  1179.  
  1180.     1  0  0  0
  1181.     0  a  0  0
  1182.     0  0  b  c
  1183.     0  0  f  0
  1184.  
  1185.     where:
  1186.     a = the aspect ratio (width / height of screen)
  1187.     b = f * (yon / (yon - hither))
  1188.     c = -f * (yon * hither / (yon - hither))
  1189.     f = sin(aov / 2) / cos(aov / 2)
  1190.     aov = angle of view
  1191.     yon = distance to far clipping plane
  1192.     hither = distance to near clipping plane
  1193.  
  1194.     These values allow me to clip using:
  1195.     -W < X < W
  1196.     -W < Y < W
  1197.     0 < Z < W
  1198.  
  1199.     After clipping, divide X and Y by W and multiply by the width and
  1200.     height of your screen to get final screen coordinates.
  1201.  
  1202.  
  1203.  
  1204. 19. Writing a byte, word, dword and other weird things
  1205. ------------------------------------------------------
  1206.  
  1207. Now to a weird thing on the Pentium. The Pentium has a so called Write-Back
  1208. cache. Well, the fact that the Pentium has a Write-Back cache is not weird at
  1209. all. It's how the Write-Back cache works in practice that is weird if you are
  1210. used to a Write-Trough cache that is used on the 486.
  1211.  
  1212. Write-Trough:
  1213.     When we write a byte to memory the byte is always written to RAM. If that
  1214.     same byte is also present in the cache, the byte in the cache is also
  1215.     updated.
  1216.  
  1217. Write-Back:
  1218.     When we write a byte to memory the byte is only written to RAM if the
  1219.     same byte is not present in the cache. If the byte is present in the
  1220.     cache, only the cache will be updated. It is first when a cacheline is
  1221.     pushed out from the cache that the whole cacheline will be written to
  1222.     RAM.
  1223.  
  1224. I have done tests on my system (Pentium 120, L1:8+8k, L2:256k) using the
  1225. time stamp counter to see how it actually behaves. These are the results:
  1226.  
  1227. Writing to a byte (or aligned word or dword) that is not present in the L1
  1228. cache takes 8 clock ticks (no matter if the byte is present in the L2 cache).
  1229. If the byte is present in the L1 cache, the same "mov" instruction takes the
  1230. theoretical 0.5 clock tick.
  1231.  
  1232. This is very interesting and potentially useful. If we e.g. manage to keep
  1233. the cacheline where we have our memory variables in the L1 cache, we can
  1234. write to them at the same speed as writing to a register. This could be very
  1235. useful in the case of a Phong-texture or Phong-texture-bump inner loop where
  1236. we need to interpolate many variables and only have 7 registers.
  1237.  
  1238. The problem is that our cacheline will be pushed out from the cache as soon
  1239. as we start getting cache misses when reading the texture data. Then we are
  1240. back at 8 clock tick per write. To fix this we must read a byte from our
  1241. cacheline so that it won't be marked as old and thrown out. But this is
  1242. usually what we do anyway. We read a variable, interpolates it, uses it and
  1243. writes it back.
  1244.  
  1245. Juan Carlos Arevalo Baeza presented in an article to comp.graphics.algorithms
  1246. another way to make use of the Write-Back cache in a texture mapping inner
  1247. loop. The idea is to ensure that the destination pixel written is always
  1248. present in the cache. This is done by reading a byte from the destination
  1249. cacheline first:
  1250.  
  1251.      ; edi = ptr to first destination pixel (+1) to plot
  1252.      ; esi = ptr to last destination pixel to plot
  1253.      ; The scanline is plotted from right to left
  1254.  
  1255.       push esi
  1256.       mov  al,[edi-1]    ; read the first byte into the cache.
  1257.  
  1258.     @@L1:
  1259.       lea  esi,[edi-32]
  1260.       cmp  esi,[esp]
  1261.       jae  @@C
  1262.       mov  esi,[esp]
  1263.     @@C:
  1264.       mov  al,[esi]      ; read the last byte of the 32-byte chunk.
  1265.     @@L:
  1266.       mov  al,[edx]
  1267.       add  ebx,ecx
  1268.       adc  edx,ebp
  1269.       dec  edi
  1270.       mov  dh,bh
  1271.       cmp  edi,esi
  1272.       mov  [edi],al
  1273.       jne  @@L
  1274.  
  1275.       cmp  edi,[esp]
  1276.       jne  @@L1
  1277.  
  1278.       pop  esi
  1279.  
  1280.     This ensures that whenever you write a pixel, that address is already in
  1281.     the cache, and that's a lot faster. A LOT. My P90 takes 20-40 cycles to
  1282.     read a cache line, so that's around 1 more cycle per pixel. Problems:
  1283.     when painting polys, rows of very few pixels (let's say 1-8 pixels) are
  1284.     the most common, and those don't feel so good about this loop. You can
  1285.     always have two loops for the different lengths.
  1286.  
  1287.  
  1288. Another way to speed up writes (that also works on 486) is to collect 4
  1289. pixels in a 32 bit register and write all 4 pixels at a time as a aligned
  1290. dword. This will split the 8 clock tick delay on all 4 pixels making the
  1291. delay only 2 clock ticks per pixel. This method will almost always gain speed
  1292. especially if the scanlines are long.
  1293.  
  1294.  
  1295.  
  1296. 20. The data cache
  1297. ------------------
  1298.  
  1299. Although it is fun optimizing inner loops there are other important factors
  1300. that one should look at. With the Pentium processor the cache aspects are
  1301. very important. Maybe more important than the speed of the inner loop. Don't
  1302. know how long this is true though as newer processors seems to get bigger and
  1303. bigger caches that probably will become smarter also.
  1304.  
  1305. The general idea of the cache is:
  1306. When the CPU has decoded an instruction that needs to get a variable from
  1307. memory, the CPU first checks the cache to see if the variable is already
  1308. in the cache. If it is there the CPU reads the variable from the cache.
  1309. This is called a cache hit. If the variable is not in the cache the CPU first
  1310. has to wait for the data to be read from RAM (or the secondary cache, L2)
  1311. into the cache and first after that get the variable from the cache. The
  1312. cache always loads a full cacheline at a time so this will take a few clock
  1313. ticks. A cacheline is 16 byte on a 486 and 32 byte on Pentium. The advantage
  1314. of this is when reading byte after byte from the memory, the data will most
  1315. of the time already be loaded into the cache because we have accessed the
  1316. same cacheline just before. Also a cacheline is always aligned on 16 byte
  1317. on the 486 and on 32 byte on the Pentium.
  1318.  
  1319. I did a few tests on my system (Pentium 120 MHz, L1 cache 8+8k, L2 cache
  1320. 256k) using the time stamp counter to check the actual time for loading a
  1321. cacheline. In the first test I flushed the L2 cache so that each cacheline
  1322. must be read all the way from RAM. This was done by allocating a 256k memory
  1323. chunk and read each byte of that first. This would cause the memory I did the
  1324. test on to be pushed out of the L2 cache. The testloop looked like this:
  1325.  
  1326.     mov  ecx, 1000
  1327.   next:
  1328.     mov  al, [esi]
  1329.     add  esi, ofs
  1330.     dec  ecx
  1331.     jnz  next
  1332.  
  1333. The overhead of the loop was first timed by replacing the "mov al, [esi]"
  1334. by "mov al, cl". The loop ran at exactly 2 clock tick per turn. The "ofs"
  1335. value was replaced for each run with 1, 2, 4, 8, 16, 32, 64, ... In the
  1336. second test I first forced the L2 cache to load the memory by reading each
  1337. byte of a 128k memory chunk and then run the testloop on the same memory.
  1338. Here are the results of both tests:
  1339.  
  1340.  
  1341.  clock ticks
  1342.                                                               * *
  1343.     |                                          *  *  *  *  *
  1344.  40 +                              *  *  *  *
  1345.     |                             *
  1346.  35 +                   from RAM *
  1347.     |                           *
  1348.  30 +                          *
  1349.     |                          *
  1350.  25 +                         *
  1351.     |                        *
  1352.  20 +                       *      +  +  +  +  +  +  +  +  +  + +
  1353.     |                      *      +
  1354.  15 +                     *     +
  1355.     |                   *      +  from L2 cache
  1356.  10 +                  *     +
  1357.     |                 *   +
  1358.   5 +               *  +
  1359.     |            * +
  1360.   0 + -----+-----+-----+-----+-----+-----+-----+-----+-----+-----  ofs
  1361.     1      2     4     8    16    32    64    128   256   512
  1362.  
  1363.  
  1364. So this tells me that it takes 40-45 clock ticks minimum to load a cacheline
  1365. all the way from RAM and exactly 18 clock ticks from the L2 cache. When "ofs"
  1366. was 1 the "mov al, [esi]" ran at 2.0 ticks when loading from RAM and 1.1
  1367. ticks from the L2 cache. 0.5+40/32=1.75 and 0.5+18/32=1.06 so this makes
  1368. sense.
  1369.  
  1370. This is pretty scary!  18 clock ticks to load a cacheline from the L2 cache.
  1371. 18 clock ticks minimum for the inner loops if we assume that a cacheline must
  1372. be filled for each byte read. Ouch!
  1373.  
  1374. So in the case of a texture mapper where we might be reading texels in a
  1375. vertical line in the bitmap, the inner loop will be accessing pixels that
  1376. are >256 bytes apart. The CPU will then be busy filling cachelines for each
  1377. texel. A 64k bitmap won't fit inside a 8k cache, you know. So what can we do?
  1378. Well, we can wait on Intel to invent bigger caches or we might consider
  1379. storing our bitmaps some other, more cache friendly way.
  1380.  
  1381. I got an interesting tip from Otto Chrons on channel #coders the other day
  1382. about this. He said that one should store the bitmap as a set of tiles, say
  1383. 8 x 8 pixels instead of the usual 256 x 256 pixel. This makes perfect sense.
  1384. It would mean that a small part of the bitmap (8 x 4 pixel) would fit in the
  1385. same 32 byte cacheline. This way, new cachelines don't need to be loaded that
  1386. often when reading pixels in a vertical line in the bitmap.
  1387.  
  1388. The following was suggested in a mail to me by Dare Manojlovic:
  1389.  
  1390.  
  1391.     If you are saving bitmap as a set of tiles (8*4) the inner loop wouldn't
  1392.     have to be more complicated (this is my opinion - not yet tested).
  1393.  
  1394.     For example, let's say that we have u&v texture coordinates, we only have
  1395.     to reorder bits to get the correct address (before the inner loop):
  1396.        Normally for a bitmap of 256*256 the texel address would look like:
  1397.        EAX                           AH            AL
  1398.         oooo oooo    oooo oooo    oooo oooo     oooo oooo
  1399.                                 v coordinate   u coordinate
  1400.  
  1401.        And now:
  1402.        EAX                           AH            AL
  1403.         oooo oooo    oooo oooo    oooo oooo    oooo oooo
  1404.          v(other 6 bits)  u(other 5 bits) v(lower 2 bits) u(lower 3 bits)
  1405.  
  1406.     Adding a constant value,that is also converted, in the loop shouldn't be
  1407.     a problem.
  1408.  
  1409.     Now, as I understand cache loading procedure,it always loads 32 bytes of
  1410.     data (Pentium), so the whole bitmap tile of (8*4 pixels) will be in cache.
  1411.     Of course bitmap tile must be 32 bytes aligned.
  1412.     This would also work faster on 486 where cache is loaded with 16 bytes.
  1413.  
  1414.  
  1415. There is a small problem to the above method. We can't just add a constant
  1416. value to a number in this format (even if they both are converted). This
  1417. is because there is a gap between the bits. We must make the bits jump over
  1418. the gap to make the add correct. There is a simple solution to this problem
  1419. though. Just fill the gap with 1:s before adding the constant value. This
  1420. will cause the bit to jump over the gap. Filling the gap is done with a
  1421. bitwise OR instruction.
  1422.  
  1423. Converting u and v (16:16 bit) to this format can be done with the following
  1424. code:
  1425.  
  1426.     int uc = (u & 0x0007ffff) | ((u<<2) & 0xffe00000);
  1427.     int vc = (v & 0x0003ffff) | ((v<<5) & 0xff800000);
  1428.  
  1429.  
  1430.     ; eax = u  --------wwwwwwwwffffffffffffffff  (w=whole, f=fractional)
  1431.     ; ebx = v  --------wwwwwwwwffffffffffffffff
  1432.     ; ecx = scratch register
  1433.     mov   ecx, eax
  1434.     shl   eax, 2
  1435.     and   ecx, 00000000000001111111111111111111b
  1436.     and   eax, 11111111111000000000000000000000b
  1437.     or    eax, ecx
  1438.     mov   ecx, ebx
  1439.     shl   ebx, 5
  1440.     and   ecx, 00000000000000111111111111111111b
  1441.     and   ebx, 11111111100000000000000000000000b
  1442.     or    ebx, ecx
  1443.     ; eax = u  ------wwwww--wwwffffffffffffffff
  1444.     ; ebx = v  ---wwwwww-----wwffffffffffffffff
  1445.  
  1446.  
  1447. Adding dudx and dvdx to u and v in this format can be done with the following
  1448. code (all variables are in the converterd format):
  1449.  
  1450.     uc = (uc | 0x00180000) + dudx;
  1451.     vc = (vc | 0x007c0000) + dvdx;
  1452.  
  1453.  
  1454.     ; eax = u  ------wwwww--wwwffffffffffffffff
  1455.     ; ebx = v  ---wwwwww-----wwffffffffffffffff
  1456.     ; dudx, dvdx = 16:16 bit converted to this format
  1457.     or    eax, 00000000000110000000000000000000b    ; fill the bit-gap in u
  1458.     or    ebx, 00000000011111000000000000000000b    ; fill the bit-gap in v
  1459.     add   eax, [dudx]
  1460.     add   ebx, [dvdx]
  1461.  
  1462.  
  1463. In a mail sent to me, Russel Simmons preresented the following method to
  1464. reorder the bits to acheive a simpler inner loop by eliminating a bit-gap:
  1465.  
  1466.  
  1467.     In one post, someone suggested a bit structure to find the corect
  1468.     position in your tiled texture given u and v. He suggested something
  1469.     like:
  1470.  
  1471.     high bits of v | high bits of u | low bits of v | low bits of u
  1472.  
  1473.     This way the high bits of u and v determine which tile our texel is in,
  1474.     and the low bits of u and v determine where in our tile the texel is.
  1475.     If we store our tiles in a different manner, we can simplify this to:
  1476.  
  1477.     high bits of u | high bits of v | low bits of v | low bits of u
  1478.  
  1479.     which is in other words:
  1480.  
  1481.     high bits of u | all bits of v | low bits of u
  1482.  
  1483.     In order to facilitate this, instead of storing our tiles in this order:
  1484.  
  1485.     -------------
  1486.     | 0| 1| 2| 3| ...  (here i am showing the upper 4x4 tiles of a 256x256
  1487.     -------------       texture store in 8x8 tiles)
  1488.     |32|33|34|35| ...
  1489.     -------------       Original Method
  1490.     |64|65|66|67| ...
  1491.     -------------
  1492.     |96|97|98|99| ...
  1493.     -------------
  1494.     |  |  |  |  |
  1495.  
  1496.     store them in this order:
  1497.  
  1498.     -------------
  1499.     | 0|32|64|96| ...  (here i am showing the upper 4x4 tiles of a 256x256
  1500.     -------------       texture store in 8x8 tiles)
  1501.     | 1|33|65|97| ...
  1502.     -------------       New Method, in order to acheive a simpler inner loop
  1503.     | 2|34|66|98| ...
  1504.     -------------
  1505.     | 3|35|67|99| ...
  1506.     -------------
  1507.     |  |  |  |  |
  1508.  
  1509.     Also, if we are storing our bitmap in a tiled fashion, then it would
  1510.     greatly improve our cache performance if we can back and forth across
  1511.     scan lines.. in other words alternate the direction we scan across lines.
  1512.     Say we have just scanned forward across one scan line. If we start
  1513.     backwards across the next scan line, we are likely to be pulling texels
  1514.     from the same tiles as we were at the end of the previous scan line.
  1515.  
  1516.  
  1517. The last part about alternating the drawing direction is definitely something
  1518. to try out!
  1519.  
  1520. I was hoping I would be able to present some code here that uses all these
  1521. techniques and 16:16 bit interpolation in a slick inner loop but due to lack
  1522. of time and the fact that I'm fed up with this document, I leave this to you.
  1523.  
  1524.  
  1525.  
  1526. 21. The code cache
  1527. ------------------
  1528.  
  1529. The cool thing about Pentiums is that it can execute two instructions in
  1530. parallel. This is called instruction pairing. But there is a lot of rules
  1531. that must be fulfilled for the pairing to take place. One rule is that both
  1532. instructions must already be in the code cache. This means that the first
  1533. time trough a inner loop, no instructions will pair. There is one exception
  1534. to this rule. If the first instruction is a 1 byte instruction, e.g. inc eax,
  1535. and the other is a simple instruction, then they will pair the first time.
  1536.  
  1537. If by chance our inner loop happens to be in the code cache, by modifying an
  1538. instruction in the inner loop (selfmodifying code) the cacheline where we
  1539. did the modification will be marked as not up to date. So that cacheline
  1540. must be loaded into the cache again before we can execute the inner loop
  1541. again. Loading of code cachelines seems to be exceptionally slow also. In
  1542. other words, we have found yet another source of delay.
  1543.  
  1544. So to have a completely unrolled loop that almost fills up the whole code
  1545. cache and also is selfmodifying is a pretty bad idea on the Pentium. On the
  1546. other hand, we are not modifying the loop for each scanline so chances are
  1547. that parts of it will be in the code cache from drawing the previous
  1548. scanline.
  1549.  
  1550.  
  1551.  
  1552. 22. Some pairing rules
  1553. ----------------------
  1554.  
  1555. As mentioned above, the Pentium can execute two instructions in parallel.
  1556. This is possible because the CPU has dual integer pipelines, they are
  1557. called the U and V pipelines. The Pentium has a so called superscalar
  1558. architecture. The U pipeline is fully equipped and can execute all integer
  1559. instructions. The V pipeline on the other hand is a bit crippled and can only
  1560. execute simple, RISC type instructions.
  1561.  
  1562. Simple instructions are:
  1563.  
  1564.  mov, inc, dec, add, adc, sub, sbb,
  1565.  and, or, xor, cmp, test, push, pop,
  1566.  lea, jmp, call, jcc, nop, sar, sal,
  1567.  shl, shr, rol, ror, (rcl), (rcr)
  1568.  
  1569. (What I've heard there are different opinions on if the shift/rotate
  1570. instructions are pairable or not. The book I have here states that these
  1571. instructions are pairable but can only execute in the U pipeline)
  1572.  
  1573.  
  1574. The first pairing rule is that both instructions must be simple instructions.
  1575. Also, no segment registers can be involved in the instructions.
  1576.  
  1577. Another rule is that the two instructions must be completely independent of
  1578. each other. Also they must not write to the same destination register/memory.
  1579. They can read from the same register though. Here are some examples:
  1580.  
  1581.     add   ecx, eax      ; store result in ecx
  1582.     add   edx, ecx      ; get result from ecx. No pairing!
  1583.  
  1584.     mov   ecx, eax
  1585.     mov   edx, ecx      ; No pairing!
  1586.  
  1587.     mov   al, bh        ; al and ah is in the same register
  1588.     mov   ah, ch        ; No pairing!
  1589.  
  1590.  
  1591.     mov   ecx, eax      ; read from the same register
  1592.     mov   edx, eax      ; Pairs ok.
  1593.  
  1594.     mov   ecx, eax      ; note eax in this example
  1595.     add   eax, edx      ; Pairs ok.
  1596.  
  1597. There are two exception to this rule. Namely the flag register and the stack
  1598. pointer. Intel has been kind enough to optimize these.
  1599.  
  1600.     dec   ecx           ; modifies the flag register
  1601.     jnz   @@inner       ; Pairs ok.
  1602.  
  1603.     push  eax           ; both instructions are accessing esp
  1604.     push  ebx           ; Pairs ok.
  1605.  
  1606.  
  1607. So for example the loop we used to calculate the lookup table with, all
  1608. instructions are simple and not dependent on the previous one. The 8
  1609. instructions should execute in 4 clock ticks.
  1610.  
  1611.  @@mklookup:
  1612.     mov   eax, ecx
  1613.     add   ecx, edi      ; Pairs ok.
  1614.     mov   al, bh
  1615.     add   ebx, esi      ; Pairs ok.
  1616.     mov   [edx], eax
  1617.     add   edx, 4        ; Pairs ok.
  1618.     dec   ebp
  1619.     jnz   @@mklookup    ; Pairs ok.
  1620.  
  1621.  
  1622.  
  1623. 23. Pipeline delays
  1624. -------------------
  1625.  
  1626. There are a whole bunch of these that will delay the pipelines:
  1627.  
  1628.  - data cache memory bank conflict
  1629.  - address generation interlock, AGI
  1630.  - prefix byte delay
  1631.  - sequencing delay
  1632.  
  1633. I personally think that the AGI is most important to consider in the case
  1634. of tight inner loops. Because that is what's happening in a inner loop, where
  1635. we are calculating an address and need it right away to access some data.
  1636. There will be a AGI delay if a register used in a effective address
  1637. calculation is modified in the previous clock cycle. So if we have our
  1638. instructions nicely pairing we might have to put 3 instructions in between to
  1639. avoid the AGI delay.
  1640.  
  1641.     add   esi, ebx      ; Move the array pointer.
  1642.     mov   eax, [esi+8]  ; AGI delay. You just modified esi.
  1643.  
  1644.  
  1645.     add   esi, ebx      ; Move the array pointer.
  1646.     add   ebx, ecx      ; Do something useful here
  1647.     inc   edi           ;  "
  1648.     add   ebp, 4        ;  "
  1649.     mov   eax, [esi+8]  ; Now it's OK to access the data. No AGI delay.
  1650.  
  1651.  
  1652. If you don't have any useful instructions to fill out the gap with you could
  1653. try to swap the two instructions so that you access the data first and then
  1654. modify the index register.
  1655.  
  1656.     mov   eax, [esi+8]
  1657.     add   esi, ebx      ; Pairs ok. No AGI delay.
  1658.  
  1659.  
  1660.  
  1661. There are a lot more rules one must follow so I suggest you buy a good book
  1662. on the subject. I don't know of any free info about this on the net as of
  1663. this writing. Maybe you'll find something at Intel's www-site
  1664. (http://www.intel.com). Anyway, a book that got me started was: "Pentium
  1665. Processor Optimization Tools" by Michael L. Schmit  ISBN 0-12-627230-1
  1666. This book has a few minor errors and some of the explanations are a bit
  1667. cryptic but it is a good starting point. The way to really learn is to get
  1668. the basics from e.g. a book and then time actual code to see what is faster
  1669. and what's not.
  1670.  
  1671.  
  1672.  
  1673. 24. The time stamp counter
  1674. --------------------------
  1675.  
  1676. The Pentium has a built in 64 bit counter called the Time Stamp Counter that
  1677. is incremented by 1 for each clock tick. To read the counter you use the
  1678. semi-undocumented instruction RDTSC (db 0fh,31h). This will load the low 32
  1679. bit of the counter into EAX and the high 32 bit into EDX. Perfect for timing
  1680. code!
  1681.  
  1682.     ; First time the overhead of doing the RDTSC instruction
  1683.     db      0fh,31h         ; hex opcode for RDTSC
  1684.     mov     ebx, eax        ; save low 32 bit in ebx
  1685.     db      0fh,31h
  1686.     sub     eax, ebx        ; overhead = end - start
  1687.     mov     [oh_low], eax
  1688.  
  1689.     ; Now do the actual timing
  1690.     db      0fh,31h
  1691.     mov     [co_low], eax
  1692.     mov     [co_hi], edx
  1693.  
  1694.     ; Run some inner loop here of whatever you want to time
  1695.  
  1696.     db      0fh,31h
  1697.     sub     eax, [co_low]   ; ticks = end - start
  1698.     sbb     edx, [co_hi]
  1699.     sub     eax, [oh_low]   ; subtract overhead
  1700.     sbb     edx, 0
  1701.     ; Number of clock ticks is now in  edx:eax
  1702.  
  1703.  
  1704. You'll notice that I first time the overhead of doing the RDTSC instruction.
  1705. This might be a bit overkill but it's no harm in doing it. Note also that I
  1706. ignore the high 32 bit. The overhead should not be more than 2^32 clock
  1707. ticks anyway. The RDTSC can be a privileged instruction under some extenders
  1708. (?) but still be available (under the control of the extender) so there might
  1709. actually be a overhead to time.
  1710.  
  1711. You can usually ignore the high 32 bit. Using only the low 32 bit will allow
  1712. a maximum of 2^32 clock ticks which is 35 seconds on a Pentium 120 MHz.
  1713.  
  1714. When you are timing your code e.g. when you have done some optimizations on
  1715. your texture mapper, don't time just one triangle over and over. Time how
  1716. long it takes to draw a complete object with hundreds (thousands) of
  1717. triangles. Then you'll know if that optimization made any difference.
  1718.  
  1719.  
  1720.  
  1721. 25. Branch prediction
  1722. ---------------------
  1723.  
  1724. The Pentium has some sort of lookup table called the Branch Target Buffer
  1725. (BTB) in which it stores the last 256 branches. With this it tries to
  1726. determine the destination for each jump or call. This is done by keeping a
  1727. history of whether a jump was taken or not the last time it was executed. If
  1728. the prediction is correct then a conditional jump takes only 1 clock tick to
  1729. execute.
  1730.  
  1731. Because the history mechanism only remembers the last time the jump was
  1732. executed, the prediction will always fail if we jump different each time.
  1733. There is a 4-5 clock tick delay if the prediction fails.
  1734.  
  1735. The branch prediction takes place in the second stage of the instruction
  1736. pipeline and predicts if whether a branch will be taken or not and its
  1737. destination. Then it starts filling the other instruction prefetch queue
  1738. with instructions from the branch destination. If the prediction was wrong,
  1739. then both prefetch queue must be flushed and prefetching restarted.
  1740.  
  1741. So to avoid this delay you should strive to use simple loops that always
  1742. takes the jump or always not takes the jump. Not like the following that
  1743. jumps different depending on the carry flag.
  1744.  
  1745.  
  1746.     jmp   @@inner
  1747.   @@extra:
  1748.     ....                ; Do something extra when we get carry overflow
  1749.     dec   ebp
  1750.     jz    @@done
  1751.   @@inner:
  1752.     ....                ; Do something useful here
  1753.     add   eax, ebx
  1754.     jc    @@extra       ; Jump on carry overflow
  1755.     dec   ebp
  1756.     jnz   @@inner
  1757.   @@done:
  1758.  
  1759. In this loop it's the 'jc @@extra' instruction that will mess up the branch
  1760. prediction. Sometimes the jump will be taken and sometimes not. The typical
  1761. way of doing masking with compares and jumps has this problem also.
  1762.  
  1763.  
  1764.  
  1765. 26. Reference
  1766. -------------
  1767.  
  1768. Most of the Pentium specific information on optimization was found in the
  1769. book: "Pentium Processor Optimization Tools" by Michael L. Schmit
  1770. ISBN 0-12-627230-1
  1771.  
  1772.  
  1773.  
  1774. 27. Where to go from here
  1775. -------------------------
  1776.  
  1777. When you have implemented your texture mapper you automatically also have
  1778. Phong shading and environment mapping. It's only a matter of making a
  1779. suitable bitmap and to use the normal vectors at each triangle vertex to get
  1780. the u and v values.
  1781.  
  1782. From there the step is not far from combining Phong shading and texture
  1783. mapping. And then adding bumps to all this. The only difficult part is that
  1784. you need to interpolate 4 variables in the inner loop when you do
  1785. Phong-texture, environment-bump or Phong-texture-bump and still have
  1786. registers left for pointers and loop counter. These shadings can't really be
  1787. called "fast" as the inner loops will become pretty ugly. They can definitely
  1788. be called real time though.
  1789.  
  1790.  
  1791.  
  1792. 28. Credits and greetings
  1793. -------------------------
  1794.  
  1795. Juan Carlos Arevalo Baeza (JCAB/Iguana-VangeliSTeam) <jarevalo@daimi.aau.dk>
  1796. Wilco Dijkstra                      <wdijkstr@hzsbg01.att.com>
  1797. Kevin Baca                          <kbaca@skygames.com>
  1798. Sean L. Palmer                      <sean@delta.com>
  1799. Tiziano Sardone                     <tiz@mail.skylink.it>
  1800. Mark Pursey                         <nerner@world.net>
  1801. Dare Manojlovic                     <tangor@celje.eunet.si>
  1802. Russel Simmons   (Armitage/Beyond)  <resimmon@uiuc.edu>
  1803. Aatu Koskensilta (Zaphod.B)         <zaphod@sci.fi>
  1804. Otto Chrons      (OCoke)    (a legend)
  1805. Nix/Logic Design            (a cool coder)
  1806. Phil Carmody     (FatPhil)  (The optimizing guru, why all this silence?)
  1807. Jmagic/Complex              (another legend)
  1808. MacFeenix                   (you are young)
  1809. BX                          (keep on coding)
  1810. thefear                     (a cool swede)
  1811. John Gronvall               (MIPS R8000 rules!)
  1812. LoZEr                       (when will PacMan for Linux be out?)
  1813. Addict, Damac, Dice, Doom, Swallow, Wode / Doomsday  (a bunch of finns ;)
  1814.  
  1815.  
  1816. When I started out writing this document I didn't know half of what I now
  1817. know about texture mapping. I've learned a lot and this is much because of
  1818. those 12 first persons in the credits and greetings list. Thanks a lot for
  1819. the help. I hope that the readers of this document also will learn something.
  1820.  
  1821. If you truly find this document useful, you could consider giving me a small
  1822. greeting in your production. That would be cool.
  1823.  
  1824. <EOF>
  1825.